上一篇，我們談了 Knapsack Problem。
假設行李箱只能裝 20 公斤，而每件物品都有：

• 重量
• 價值

我們真正想解的是：

在有限容量裡，應該選哪些東西，才能得到最大的總價值？

所以有些物品最後可能不會被選進去。
但今天換一個場景。
假設你不是在整理自己的旅行行李，而是在物流中心工作。
倉庫裡有一堆貨物 [8, 7, 6, 5, 4, 3]，每個數字代表一件貨物占用的空間。

現在每台貨車最多只能裝 10，問題是：

這些貨物全部都必須送走，最少需要幾台貨車？

這次不能說：

8 太大了，我不帶

也不能只挑「價值最高」的貨物。
因為條件變成：

所有貨物都必須被分配到某一台貨車裡

這就是今天要談的：

Bin Packing Problem

Knapsack 和 Bin Packing 看起來很像，問題卻不同

Knapsack 和 Bin Packing 都會出現：

有限容量 + 不同大小的物品

所以它們第一眼看起來很像，但兩個問題的最佳化目標不一樣。
Knapsack 問：

一個容量有限的容器裡，哪些東西值得放？

例如：

容量 = 10

A：weight 6，value 10
B：weight 4，value 8
C：weight 5，value 9

我們可能最後只選 A + B，C 沒有被選到也沒有關係。
但 Bin Packing 不一樣。
假設有貨物：[6, 4, 5, 5]。
每台貨車容量：10。

所有貨物都必須送走，我們要找的是一種分配方式：

貨車 1：6 + 4 = 10
貨車 2：5 + 5 = 10

所以只需要 2 台。
這次的最佳化目標不是最大化 value而是最小化使用的貨車數量。
可以把它簡化成：

Knapsack
→ 容器固定
→ 可以捨棄部分物品
→ 最大化價值

Bin Packing
→ 物品全部都要裝
→ 容器數量可以增加
→ 最小化容器數量

問題看起來只改了一點，求解方式卻完全不同。

容量還是在限制我們

假設每台貨車的容量是：10。
貨物依序是：[6, 5, 4, 3, 2]。

我們不能把 6 + 5 放在一起，因為 11 > 10。
因此每次放入貨物時，都必須滿足：

目前已使用容量 + 新貨物大小 <= capacity

那麼我們就可以得出：

• 貨車 1：6 + 4 = 10
• 貨車 2：5 + 3 + 2 = 10

這組貨物可以被裝進 2 台貨車。
乍看之下好像不難，只要看到還有空間，就塞進去。
問題是：

到底該塞進哪一台？

不同的放法，可能需要不同數量的貨車

假設每台貨車容量都是：10。
現在有幾件貨物：[4, 8, 1, 4, 2, 1]。

如果我們分成：

• 貨車 1：4 + 1 + 4 + 1 = 10
• 貨車 2：8 + 2 = 10

只需要 2 台貨車。
但我們在真正處理貨物時，通常不是一開始就知道這個漂亮的組合。

貨物可能是一件一件進來：

4
↓
8
↓
1
↓
4
↓
2
↓
1

每次看到一件新貨物，我們都要決定：

放進哪台已經存在的貨車？

如果放不下：

要不要再開一台新的貨車？

這就是 Bin Packing 麻煩的地方。
你不是只需要確認：

能不能放？

還要考慮：

現在放在這裡，會不會讓後面的貨物更難安排？

這種問題我們在前兩篇其實已經看過了。
Day 20 談 Greedy 時，我們就知道：

現在看起來最好的選擇，不一定會產生全域最佳解

Bin Packing 又把這個問題放大了一次。

最直接的方法：First Fit

面對這種問題，一個很自然的方法叫做：

First Fit

規則很簡單，每當一件新貨物進來時：

從第一台貨車開始檢查，找到第一台還放得下它的貨車，就放進去

如果所有貨車都放不下：

開一台新的貨車

例如 capacity：10。
貨物依序：[6, 4, 5, 3, 2]。

第一件 6。
目前沒有貨車，所以開一台：

貨車 1：[6]
剩餘：4

接著是 4，貨車 1 放得下：

貨車 1：[6, 4]
剩餘：0

接著 5，貨車 1 已經滿了，所以開新貨車：

貨車 2：[5]
剩餘：5

接著 3，從第一台開始找。
貨車 1 放不下。
貨車 2 可以：

貨車 2：[5, 3]
剩餘：2

最後 2，一樣從第一台開始找。
貨車 1 不行，貨車 2 可以：

貨車 2：[5, 3, 2]
剩餘：0

最後結果：

貨車 1：[6, 4]
貨車 2：[5, 3, 2]

使用 2 台貨車。
First Fit 的好處很明顯：

規則非常簡單

我們不需要預先算出所有組合。
每一件貨物進來，就立刻知道該怎麼處理。

但為什麼一定要放進「第一台」？

First Fit 有一個特別的地方，它並不是在宣稱：

第一台可以放的貨車，一定是最好的選擇

它只是說：

找到可以放的地方，就先放進去

這是一種策略，但我們可以設計另一種策略。
例如：

與其找第一台放得下的，不如找「放進去之後最滿」的那一台

這就是另一個常見方法：

Best Fit

Best Fit：盡可能把剩餘空間填滿

一樣假設每台貨車容量：10。
目前有：

貨車 A：已使用 4
剩餘 6

貨車 B：已使用 7
剩餘 3

現在來了一件大小 2。

兩台都放得下。
如果使用 First Fit，而且 A 是第一台：

A：4 + 2 = 6
剩餘 4

但 Best Fit 會比較：

• 放進 A → 剩 4
• 放進 B → 剩 1

它會選 B，因為放進 B 之後，剩餘空間最小。
也就是：

盡量把某個容器填滿，而不是讓很多容器都留下零碎空間

直覺上很合理，我們可能會想：

既然每台貨車容量有限，那就盡量把已經開出去的貨車塞滿

但這裡又遇到了熟悉的問題。

「看起來更有效率」不等於「一定最佳」

Best Fit 聽起來甚至比 First Fit 更聰明。
因為它會比較所有能放的貨車，再挑剩餘空間最小的。
可是這仍然不代表：

Best Fit 一定能找到最少貨車數

原因和 Greedy 很像。
現在把某台貨車填得很滿，可能看起來很好。
但你不知道後面還會出現什麼貨物。
也許留下 3 的空間，正好可以容納後面的一件貨物。
如果你現在硬把它填成只剩 1，反而可能讓後面的貨物必須開一台新車。

所以 First Fit 和 Best Fit 都不是在說：

我保證得到最佳答案

它們像是在說：

我用一個相對合理、而且計算成本可以接受的方法，快速找到一個不錯的答案

這類策略有一個非常重要的名字：Heuristic。

Heuristic 不是亂猜

Heuristic 常常翻成：

啟發式方法

這個詞第一次看到可能有點抽象，但它的概念其實很生活化。
假設你正在搬家，地上有：30 個箱子。
外面有幾台容量有限的貨車。
你大概不會先坐下來說：

我要列出這 30 個箱子所有可能的分配方式，證明哪一種使用的貨車數量最少

你比較可能做的是：

• 還有位置 → 塞進去
• 這件很大 → 先處理
• 這台快滿了 → 看能不能補一件小的

這些做法未必能證明：這就是理論上的最佳解。
但它們通常能：很快得到一個夠好的解。
這就是 heuristic 的核心精神：

利用問題的特性，設計一套通常表現不錯的決策規則

為什麼不直接算出最佳答案？

看到這裡可能會有一個問題：

既然我們知道目標是「最少貨車」，為什麼不直接把最佳答案算出來？

因為當貨物數量增加時：

可能的分配方式會變得非常多

只有幾件貨物時，你也許還可以人工嘗試：

A 放車 1
B 放車 1
C 放車 2
...

看看不同排列。
但當貨物變成：

10 件
20 件
100 件
1000 件

事情很快就不再只是「多試幾次」，每件貨物都可能被放到不同容器中。
而一個決定又會影響後面的可用空間，因此可能的組合會快速增加。
這和上一篇 Knapsack 很像。
Bin Packing 的最佳化目標其實非常清楚：

所有貨物都送走
+
不超過每台貨車 capacity
+
使用最少貨車

我們完全知道自己想要什麼，困難的是：

找到那個真正的最佳答案，可能需要付出非常高的計算成本

「最佳答案」本身也有成本

這是演算法裡非常重要的一個轉折。
前面很多問題，我們可能會下意識認為：

有問題
↓
找演算法
↓
算出最佳答案

但真實世界不一定允許我們這樣做。
假設物流系統現在有：10,000 件貨物。
貨車半小時後就要出發。

理論上，你也許可以花大量計算資源，繼續搜尋：

有沒有比現在少一台貨車的排列？

但如果計算要跑好幾小時，那這個答案即使更好，也可能已經沒有用了。
因為貨車早就該出發了，所以現實中的最佳化目標往往不只一個。
表面上我們在追求最少貨車，實際上還有：

• 計算時間
• 系統成本
• 決策速度

因此工程上真正的問題可能變成：

我要不要花十倍的計算成本，只為了再少用一台貨車？

這已經不只是「會不會寫演算法」的問題，而是：

這個最佳解，值不值得我們付出取得它的成本？

First Fit 和 Best Fit 是在做取捨

現在重新看：

• First Fit
• Best Fit

它們的價值就比較容易理解了。

First Fit 的想法是：

從前面開始
↓
找到第一個能放的容器
↓
放進去

簡單、快速。

Best Fit 則多做一些比較：

找出所有放得下的容器
↓
比較放入後的剩餘容量
↓
選剩餘最少的

可能付出更多搜尋成本，希望空間使用得更緊密。
兩者都在交換不同東西：

計算成本 vs. 解的品質

這也是 heuristic 很重要的原因。
它承認了一件事：

我們有時願意接受「不保證最佳」，來換取更快、更實用的答案

順序本身也可能影響答案

Bin Packing 還有另一個很有意思的特性。
假設相同的一批貨物，只是進來的順序不同：

[2, 5, 4, 7, 1, 3]

和：

[7, 5, 4, 3, 2, 1]

即使使用完全相同的 First Fit，最後的分配結果也可能不同。
因為 First Fit 每一步都會受到目前哪些貨車已經存在和每台貨車還剩多少容量的影響。
所以有些做法會先把貨物按照大小排序，再使用類似 First Fit 的策略。

例如：

先處理大的
↓
再逐漸處理小的

直覺是：

大的貨物比較難安插，小的貨物之後比較容易拿來填空

我們今天不需要繼續深入不同 Bin Packing 演算法。
最重要的是看到：

即使最佳化目標沒變，處理順序與 heuristic 的選擇，也可能改變最後的結果

從挑選走向分配

Knapsack 問的是：在有限容量裡，哪些物品值得被選進來？

Bin Packing 則把條件改成：

所有物品都必須被安排，而且希望使用的容器越少越好

問題因此從「挑選哪些物品」，變成「怎麼分配所有物品」。

First Fit 和 Best Fit 也讓我們看到，當找到最佳答案的成本太高時，我們可能會使用 heuristic，在計算速度與答案品質之間做出取捨。

而且即使採用相同策略，物品的處理順序仍可能改變結果。這也是為什麼「先做哪一步」有時和「選擇哪個方法」同樣重要。

有限的不只空間

在 Bin Packing 裡，限制我們的是貨車或容器的空間。
但幾乎所有系統都還面對另一種有限資源：時間。

如果我們不再把貨物放進貨車，而是要把許多工作放進有限的一天，問題看起來似乎很像，卻又多了一些空間分配沒有的特性。

下一篇，我們就把有限資源從空間換成時間。

當一天能使用的時間有限，工作又該怎麼安排？